package algorithms;


/**
 * 归并排序——稳定
 * @author shhjiang_001
 * @create 2020-04-01 21:03
 */
public class Merge {
    private static Comparable[] aux;
    public static void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);

    }
    private static void sort(Comparable[] a ,int lo,int hi){
        if (hi <= lo) return;  // 递归调用的方法结束
        int mid = lo+(hi - lo)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi);
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo,j = mid+1;
        for (int k = lo;k <= hi;k++) aux[k] = a[k];
        for (int k = lo;k <= hi;k++){
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j],aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
        for (int m = 0; m < a.length;m++){
            System.out.print(a[m]+" ");
        }
        System.out.println();

    }

    private static boolean less(Comparable aux, Comparable aux1) {
        return aux.compareTo(aux1) < 0;
    }

    public static void main(String[] args) {
        Character[] a = {'M','E','R','G','E','S','O','R','T','E','X','A','M','P','L','E'};
        sort(a);
        show(a);
    }

    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
}
